



#ifndef _UNION_H_
#define _UNION_H_





typedef struct ___union__
{
	int* sets; // 集合元素数组。如果元素是正，表示该元素的根节点索引。如果是负，则是根节点，绝对值是该树的元素数量。

	int size; // 集合大小。
}Union;


#include"stl_.h"

/// <summary>
/// 分配并查集内存。
/// </summary>
/// <param name="u"></param>
/// <param name="size"></param>
void union_allocate(Union* u, int size);

/// <summary>
/// 释放并查集内存
/// </summary>
/// <param name="u"></param>
void union_deallocate(Union* u);

/// <summary>
/// 初始化并查集内存。
/// </summary>
/// <param name="u"></param>
void union_init(Union* u);

/// <summary>
/// 寻找元素的根节点序号
/// </summary>
/// <param name="u">并查集</param>
/// <param name="element">元素序号</param>
/// <returns>根节点索引</returns>
int union_find_root(Union* u, int element);

/// <summary>
/// root1，root2必须是根节点，否则并查集的结构会被破坏。
/// 使用union_find_root 可以找到元素的根节点。
/// </summary>
/// <param name="u">并查集</param>
/// <param name="root1">子集根节点</param>
/// <param name="root2">子集根节点</param>
/// <returns>根节点元素数量</returns>
int union_union(Union* u, int root1, int root2);







#endif
